package com.zFace.LRU;

import java.util.HashMap;

/**
 * LRUCache 的链表 + HashMap 实现
 *
 * @param <K>
 * @param <V>
 */
public class LRUCache<K, V> {

	private final int currentCacheSize;
	private final int cacheCapacity;
	private final HashMap<K, CacheNode> caches;
	private CacheNode first;
	private CacheNode last;

	public LRUCache(int size) {
		currentCacheSize = 0;
		this.cacheCapacity = size;
		caches = new HashMap<>(size);
	}

	public void put(K k, V v) {
		CacheNode node = caches.get(k);
		if (node == null) {
			if (caches.size() >= cacheCapacity) {
				caches.remove(last.key);
				removeLast();
			}
			node = new CacheNode();
			node.key = k;
		}
		node.value = v;
		moveToFirst(node);
		caches.put(k, node);
	}

	public Object get(K k) {
		CacheNode node = caches.get(k);
		if (node == null) {
			return null;
		}
		moveToFirst(node);
		return node.value;
	}

	public Object remove(K k) {
		CacheNode node = caches.get(k);
		if (node != null) {
			if (node.pre != null) {
				node.pre.next = node.next;
			}
			if (node.next != null) {
				node.next.pre = node.pre;
			}
			if (node == first) {
				first = node.next;
			}
			if (node == last) {
				last = node.pre;
			}
		}

		return caches.remove(k);
	}

	public void clear() {
		first = null;
		last = null;
		caches.clear();
	}

	private void moveToFirst(CacheNode node) {
		if (first == node) {
			return;
		}
		if (node.next != null) {
			node.next.pre = node.pre;
		}
		if (node.pre != null) {
			node.pre.next = node.next;
		}
		if (node == last) {
			last = last.pre;
		}
		if (first == null || last == null) {
			first = last = node;
			return;
		}

		node.next = first;
		first.pre = node;
		first = node;
		first.pre = null;
	}

	private void removeLast() {
		if (last != null) {
			last = last.pre;
			if (last == null) {
				first = null;
			} else {
				last.next = null;
			}
		}
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		CacheNode node = first;
		while (node != null) {
			sb.append(String.format("%s:%s ", node.key, node.value));
			node = node.next;
		}

		return sb.toString();
	}

	class CacheNode {
		CacheNode pre;
		CacheNode next;
		Object key;
		Object value;

		public CacheNode() {

		}
	}

	public static void main(String[] args) {

		LRUCache<Integer, String> lru = new LRUCache<>(3);

		lru.put(1, "a");    // 1:a
		System.out.println(lru);
		lru.put(2, "b");    // 2:b 1:a
		System.out.println(lru);
		lru.put(3, "c");    // 3:c 2:b 1:a
		System.out.println(lru);
		lru.put(4, "bb");   // 2:bb 1:aa 4:d
		System.out.println(lru);
		lru.put(5, "bb");   // 2:bb 1:aa 4:d
		System.out.println(lru);
		lru.put(6, "bb");   // 2:bb 1:aa 4:d
		System.out.println(lru);
		lru.put(2, "d");    // 4:d 3:c 2:b
		System.out.println(lru);
		lru.put(2, "aa");   // 1:aa 4:d 3:c
		System.out.println(lru);
		lru.put(1, "bb");   // 2:bb 1:aa 4:d
		System.out.println(lru);

	}
}